Given a node in a binary search tree, return the in-order successor of that node in the BST. If that node has no in-order successor, return null.
The successor of a node is the node with the smallest key greater than node.val.
You will have direct access to the node but not to the root of the tree. Each node will have a reference to its parent node. Below is the definition for Node:
class Node {
public int val;
public Node left;
public Node right;
public Node parent;
}
Example 1:
Input: tree = [2,1,3], node = 1 Output: 2 Explanation: 1's in-order successor node is 2. Note that both the node and the return value is of Node type.
Example 2:
Input: tree = [5,3,6,2,4,null,null,1], node = 6 Output: null Explanation: There is no in-order successor of the current node, so the answer is null.
Example 3:
Input: tree = [15,6,18,3,7,17,20,2,4,null,13,null,null,null,null,null,null,null,null,9], node = 15 Output: 17
Example 4:
Input: tree = [15,6,18,3,7,17,20,2,4,null,13,null,null,null,null,null,null,null,null,9], node = 13 Output: 15
Example 5:
Input: tree = [0], node = 0 Output: null
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -105 <= Node.val <= 105- All Nodes will have unique values.
Follow up: Could you solve it without looking up any of the node's values?
Average Rating: 4.97 (30 votes)
Solution
Successor and Predecessor
Successor = "after node", i.e. the next node in the inorder traversal, or the smallest node after the current one.
Predecessor = "before node", i.e. the previous node in the inorder traversal, or the largest node before the current one.
Approach 1: Iteration
Intuition
There are two possible situations here :
- Node has a right child, and hence its successor is somewhere lower in the tree. To find the successor, go to the right once and then as many times to the left as you could.
- Node has no right child, then its successor is somewhere upper in the tree. To find the successor, go up till the node that is left child of its parent. The answer is the parent. Beware that there could be no successor (= null successor) in such a situation.
Algorithm
-
If the node has a right child, and hence its successor is somewhere lower in the tree. Go to the right once and then as many times to the left as you could. Return the node you end up with.
-
Node has no right child, and hence its successor is somewhere upper in the tree. Go up till the node that is left child of its parent. The answer is the parent.
Implementation
Complexity Analysis
- Time complexity : O(H), where H is the height of the tree. That means O(logN) in the average case, and O(N) in the worst case, where N is the number of nodes in the tree.
- Space complexity : O(1), since no additional space is allocated during the calculation.
September 15, 2020 1:37 PM
JS recursive solution. Pretty damn proud of my code for once lmao
var inorderSuccessor = function(node) {
if (node.right) return goDown(node.right);
return goUp(node.parent, node.val);
};
function goDown(node) {
if (!node || !node.left) return node;
return goDown(node.left);
}
function goUp(node, val) {
if (!node) return node;
if (node.val > val) return node;
return goUp(node.parent, val);
}
September 16, 2020 4:07 AM
For the second situation, just go up and find the node with greater value. No need to check if left or right:
// the successor is somewhere upper in the tree
while (x.parent != null && node.val > x.parent.val) x = x.parent;
January 20, 2020 9:47 AM
Can anyone explain clearly why "Go up til the node that is the left child of its parent" logic works? I can rationalize this to myself knowing the fact but can't seem to logically explain.
Last Edit: August 26, 2019 8:10 PM
The first time I wrote almost exactly the same as the official solution:
class Solution:
def inorderSuccessor(self, node: 'Node') -> 'Node':
if node.right:
node = node.right
while node.left:
node = node.left
return node
while node.parent and node.parent.val < node.val:
node = node.parent
return node.parent
Last Edit: August 30, 2019 4:05 AM
"Given a binary search tree and a node in it"
Where is the "node in it"? Only the tree is given. Why is the method signature not the same as 285. Inorder Successor in BST?
May 23, 2021 3:42 AM
Where is the use of BST properties here? The solution will be the same for BT or BST.
class Solution:
def inorderSuccessor(self,node):
if node.right:
return self.leftmost(node.right)
p=node.parent
while p:
if node is p.left:
break
node=p
p=node.parent
return p
def leftmost(self,node):
if not node.left:
return node
return self.leftmost(node.left)
May 18, 2021 3:54 AM
This algorithm does not use the fact that the tree is a BST. An inorder traversal is the same for a tree as a binary search tree.
April 13, 2021 1:59 PM
Clear code: either right exists or not. Handled both cases well:
class Solution {
public Node inorderSuccessor(Node node) {
if (node == null) return null;
if (node.right != null) {
Node cur = node;
cur = cur.right;
while (cur.left != null) {
cur = cur.left;
}
return cur;
}
else {
Node p = node.parent;
Node cur = node;
while (p != null && p.right == cur) {
cur = p;
p = p.parent;
}
return p;
}
}
}
February 11, 2021 11:58 PM
Anyone confused? just think of the Inorder Traversal of the tree and visualize what will come after a node?
if it has right subtree the leftmost element of right subtree.
else the node which would have called it as its left subtree.
Last Edit: January 5, 2021 5:20 AM
Explanation of the logic when it has no right child, for those who need:
Pre-condition:
C1. the target node has no right child (which means its successor if exists, is above it)
About the current node:
A1. all the nodes in the subtree rooted at the current node has been visited.
[since in-order traversal guarantees the order:
left-subtree --> root (current, visited) --> right-subtree(non-existent due to C1)]
There are three cases about the parenthood of the current node:
P1. has no parent: all nodes have been visited.
(the end condition of the iteration)
P2. is its parent's right child: all the nodes in the subtree rooted at its parent has been visited.
[since in-order traversal guarantees the order:
left-subtree --> root(parent) --> right-subtree(rooted at current, visited due to A1)]
(then change current node to its parent and go on)
P3. is its parent's left child: successor is its parent.
[since in-order traversal guarantees the order:
left-subtree(rooted at current, visited due to A1, where the last step is the target node) --> root(parent, succeeds from the last step, which is the target node) --> right-subtree]
(then return its parent)
The below is my code (in Java), which I think is more understandable:
// O(H) time, O(1)space when
// has no right child (and)
// find the first ancestor that has node as its left descendant
while (node.parent != null) {
if (node == node.parent.left) return node.parent; // case 3
else node = node.parent;// case 2
}
// case 1
return null;
You don't have any submissions yet.
x
/*// Definition for a Node.class Node {public: int val; Node* left; Node* right; Node* parent;};*/class Solution {public: Node* inorderSuccessor(Node* node) { // the successor is somewhere lower in the right subtree if (node->right) { node = node->right; while (node->left) node = node->left; return node; } // the successor is somewhere upper in the tree while (node->parent && node == node->parent->right) node = node->parent; return node->parent; }};